package leetbook.string;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public static void main(String[] args) {
        String s = "abbab";
        System.out.println(new Solution2().partition(s));
    }

    public List<List<String>> partition(String s) {
        int len = s.length();
        boolean[][] isPalindrome = new boolean[len][len];
        //初始化isPalindrome
        for (int i = 0; i < len; i++) {
            isPalindrome[i][i] = true;
        }
        for (int j = 0; j < len; j++) {
            for (int i = j-1; i >= 0; i--) {
                boolean tmp = s.charAt(i)==s.charAt(j);
                if(i+1>j-1) isPalindrome[i][j] = tmp;
                else isPalindrome[i][j] = tmp&&isPalindrome[i+1][j-1];
            }
        }
        //回溯
        List<List<String>> total = new ArrayList<>();
        List<String> record = new ArrayList<>();
        backTrace(s,total,record,isPalindrome,0);
        return total;
    }

    public void backTrace(String s, List<List<String>> total, List<String> record, boolean[][] isPalindrome, int start){
        if(start==s.length()){
            total.add(new ArrayList<>(record));
            return;
        }
        //寻找每一个以start开头的回文子串
        for (int i = start; i < s.length(); i++) {
            if(isPalindrome[start][i]){
                record.add(s.substring(start,i+1));
                backTrace(s,total,record,isPalindrome,i+1);
                record.remove(record.size()-1);
            }
        }
    }
}
